package LKGF_STSX;

import java.io.File;
import java.util.*;

public class Array_ {
    /*力扣官方提供的刷题顺序----- 数组篇*/
    /*495*/
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int ans = 0;//开始时间
        int expired = 0;//结束时间
        for (int i = 0; i < timeSeries.length; ++i) {
            if (timeSeries[i] >= expired) {
                ans += duration;
            } else {
                ans += timeSeries[i] + duration - expired;
            }
            expired = timeSeries[i] + duration;
        }
        return ans;
    }
    /*414*/
    public int thirdMax(int[] nums) {
        /*tok 或数组排序*/
        Arrays.sort(nums);

        if (nums.length < 3){
            return nums[nums.length-1];
        }
        HashSet<Integer> set=new HashSet<>();
        int k=0;
        int max=0;
        for (int i = nums.length-1; i >=0 ; i--) {
            if (!set.contains(nums[i])){

                set.add(nums[i]);
                k++;
                if (k == 3){
                    max=nums[i];
                    break;
                }
            }
        }
        if(k < 3){
            return nums[nums.length-1];
        }
        return max;
    }
    /*628*/
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 3] * nums[n - 2] * nums[n - 1]);
    }

    /*645*/
    public int[] findErrorNums(int[] nums) {
        int[] errorNums = new int[2];
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (int i = 1; i <= n; i++) {
            int count = map.getOrDefault(i, 0);
            if (count == 2) {
                errorNums[0] = i;
            } else if (count == 0) {
                errorNums[1] = i;
            }
        }
        return errorNums;
    }
    /*697*/
    public int findShortestSubArray(int[] nums) {
        /*真™巧妙,我也想到了哈希表,只不过是俩个哈希表
        用的是Integer和数组定义的
        * 0代表出现次数,1代表出现起始位置,2代表最终位置*/
        Map<Integer, int[]> map = new HashMap<Integer, int[]>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (map.containsKey(nums[i])) {
                map.get(nums[i])[0]++;
                map.get(nums[i])[2] = i;
            } else {
                map.put(nums[i], new int[]{1, i, i});
            }
        }
        int maxNum = 0, minLen = 0;
        /*max代表最大次数,min最小长度*/
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] arr = entry.getValue();
            if (maxNum < arr[0]) {
                maxNum = arr[0];
                minLen = arr[2] - arr[1] + 1;
            } else if (maxNum == arr[0]) {
                if (minLen > arr[2] - arr[1] + 1) {
                    minLen = arr[2] - arr[1] + 1;
                }
            }
        }
        return minLen;
    }

    /*448*/
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> list=new LinkedList<>();
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            hashMap.put(nums[i],hashMap.getOrDefault(nums[i],0)+1);
        }
        for (int i = 1; i <= nums.length; i++) {
            if (!hashMap.containsKey(i)){
                list.add(i);
            }
        }
        return list;
    }
    /*442*/
    public List<Integer> findDuplicates(int[] nums) {
        /*天才般的想法-为什么我想不出来?*/
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            while (nums[i] != nums[nums[i] - 1]) {
                swap(nums, i, nums[i] - 1);
            }
        }
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < n; ++i) {
            if (nums[i] - 1 != i) {
                ans.add(nums[i]);
            }
        }
        return ans;
    }

    public void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
    /*41*/
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }
        for (int i = 0; i < n; ++i) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return n + 1;
    }
    /*274*/
    public int hIndex(int[] citations) {
        Arrays.sort(citations);
        int h = 0, i = citations.length - 1;
        while (i >= 0 && citations[i] > h) {
            h++;
            i--;
        }
        return h;
    }
    /*453*/
    public int minMoves(int[] nums) {
        int minNum = Arrays.stream(nums).min().getAsInt();
        int res = 0;
        for (int num : nums) {
            res += num - minNum;
        }
        return res;
    }
    /*665*/
    public boolean checkPossibility(int[] nums) {
        int n = nums.length, cnt = 0;
        for (int i = 0; i < n - 1; ++i) {
            int x = nums[i], y = nums[i + 1];
            if (x > y) {
                cnt++;
                if (cnt > 1) {
                    return false;
                }
                if (i > 0 && y < nums[i - 1]) {
                    nums[i + 1] = x;
                }
            }
        }
        return true;
    }
    /*283*/
    public void moveZeroes(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }
    /*118*/
    public List<List<Integer>> generate(int numRows) {
        //杨辉三角写法
        //   ArrayList是顺序表;
        List<List<Integer>> ret=new ArrayList<>();
        //构建一个二维数组
        List<Integer> row=new ArrayList<>();//第一行
        row.add(1);
        ret.add(row);//将第一行放进去
        for (int i = 1; i < numRows; i++) {
            //杨辉三角的第二行开始
            List<Integer> pveroe=ret.get(i-1);//获取上一行
            List<Integer> roe=new ArrayList<>();
            roe.add(1);//第一个元素置为1

            for (int j = 1; j < i; j++) {
                //每行的第一个元素和最后一个元素为1
                int x= pveroe.get(j)+pveroe.get(j-1);
                roe.add(x);
            }
            roe.add(1);//最后一个元素置为1
            ret.add(roe);
        }
        return ret;

    }
    /*119*/
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> C = new ArrayList<List<Integer>>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(C.get(i - 1).get(j - 1) + C.get(i - 1).get(j));
                }
            }
            C.add(row);
        }
        return C.get(rowIndex);
    }

    /*661*/
    public int[][] imageSmoother(int[][] img) {
        int m = img.length, n = img[0].length;
        int[][] ret = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int num = 0, sum = 0;
                for (int x = i - 1; x <= i + 1; x++) {
                    for (int y = j - 1; y <= j + 1; y++) {
                        if (x >= 0 && x < m && y >= 0 && y < n) {
                            num++;
                            sum += img[x][y];
                        }
                    }
                }
                ret[i][j] = sum / num;
            }
        }
        return ret;
    }
    /*598*/
    public int maxCount(int m, int n, int[][] ops) {
        int mina = m, minb = n;
        for (int[] op : ops) {
            mina = Math.min(mina, op[0]);
            minb = Math.min(minb, op[1]);
        }
        return mina * minb;
    }
    /*419*/
    public int countBattleships(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        int ans = 0;
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (board[i][j] == 'X') {
                    board[i][j] = '.';
                    for (int k = j + 1; k < col && board[i][k] == 'X'; ++k) {
                        board[i][k] = '.';
                    }
                    for (int k = i + 1; k < row && board[k][j] == 'X'; ++k) {
                        board[k][j] = '.';
                    }
                    ans++;
                }
            }
        }
        return ans;
    }
    /*189*/
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = Arrays.copyOf(nums,nums.length);
        for (int i = 0; i < n; ++i) {
            nums[(i + k) % n] = newArr[i];
        }
    }
    /*396*/
    public int maxRotateFunction(int[] nums) {
        int f = 0, n = nums.length, numSum = Arrays.stream(nums).sum();
        for (int i = 0; i < n; i++) {
            f += i * nums[i];
        }
        int res = f;
        for (int i = n - 1; i > 0; i--) {
            f += numSum - n * nums[i];
            res = Math.max(res, f);
        }
        return res;
    }
    /*54*/
    public static List<Integer> spiralOrder(int[][] matrix) {
        LinkedList<Integer> result = new LinkedList<>();
        if(matrix==null||matrix.length==0) return result;
        int left = 0;
        int right = matrix[0].length - 1;
        int top = 0;
        int bottom = matrix.length - 1;
        int numEle = matrix.length * matrix[0].length;

        while (numEle >= 1) {
            for (int i = left; i <= right && numEle >= 1; i++) {
                result.add(matrix[top][i]);
                numEle--;
            }
            top++;
            for (int i = top; i <= bottom && numEle >= 1; i++) {
                result.add(matrix[i][right]);
                numEle--;
            }
            right--;
            for (int i = right; i >= left && numEle >= 1; i--) {
                result.add(matrix[bottom][i]);
                numEle--;
            }
            bottom--;
            for (int i = bottom; i >= top && numEle >= 1; i--) {
                result.add(matrix[i][left]);
                numEle--;
            }
            left++;
        }
        return result;
    }
    /*59*/
    public int[][] generateMatrix(int n) {

        if (n <= 0){
            return null;
        }
        int[][] array=new int[n][n];
        int left = 0;
        int right = n-1;
        int top = 0;
        int bottom = n-1;
        int numEle = 1;
        while (numEle <= n*n){
            for (int i = left; i <= right && numEle <= n*n; i++) {
                array[top][i]=numEle;
                numEle++;
            }
            top++;
            for (int i = top; i <= bottom && numEle <= n*n ; i++) {
                array[i][right]=numEle;
                numEle++;
            }
            right--;
            for (int i = right; i >= left && numEle <= n*n; i--) {
                array[bottom][i]=numEle;
                numEle++;
            }
            bottom--;
            for (int i = bottom; i >= top && numEle <= n*n; i--) {
                array[i][left]=numEle;
                numEle++;
            }
            left++;
        }
        return array;
    }
   /*498*/
    public static int[] findDiagonalOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return new int[0];
        int m = matrix.length;
        int n = matrix[0].length;
        int[] nums = new int[m * n];

        int k = 0;
        boolean bXFlag = true;
        for (int i = 0; i < m + n; i++){// i 是 x + y 的和
            int pm = bXFlag ? m : n;
            int pn = bXFlag ? n : m;

            int x = (i < pm) ? i : pm - 1;// 确定 x y 的初始值
            int y = i - x;

            while (x >= 0 && y < pn){
                nums[k++] = bXFlag ? matrix[x][y] : matrix[y][x];
                x--;
                y++;
            }

            bXFlag = !bXFlag;
        }

        return nums;
    }
    /*566*/
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length, n = mat[0].length, x = 0;
        if(m * n != r * c) return mat;
        HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                hash.put(x++, mat[i][j]);
            }
        }
        int[][] newMat = new int[r][c];
        for(int i = 0; i < r; ++i){
            for(int j = 0; j < c; ++j){
                newMat[i][j] = hash.get(i*c + j);
            }
        }
        return newMat;
    }
    /*48*/
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int[][] matrix_new = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix[i][j] = matrix_new[i][j];
            }
        }
    }


    /*289*/
    public void gameOfLife(int[][] board) {
        int[][] newArr=new int[board.length][board[0].length];

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                newArr[i][j]=gameOfLife_func(board,i,j);
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                board[i][j]=newArr[i][j];
            }
        }
    }
    private int gameOfLife_func(int[][]board,int c,int r){
        int n=board.length,m=board[0].length;
        int count=0;
        for (int i = c-1; i <= c+1; i++) {
            for (int j = r-1; j <= r+1; j++) {
                if (i >= 0 && i < n && j >= 0&& j < m){
                    if (board[i][j] == 1)count++;
                    /*判断有几个1*/
                }
            }
        }
        boolean flag=false;
        if (board[c][r] == 1){
            count--;
            flag=true;
        }
        if (count < 2){
            return 0;
        }else if ( count == 3){
            return 1;
        }else if (count ==2 && flag){
            return 1;
        }else{
            return 0;
        }
    }

    public int[] productExceptSelf(int[] nums) {
        int mlu=1;
        int zero=0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0){
                mlu*=nums[i];
            }else {
                zero++;
            }
        }
        for (int i = 0; i < nums.length; i++) {
            if (zero > 1){
                nums[i]=0;
            }else if (zero == 1){
                if (nums[i] == 0){
                    nums[i]=mlu;
                }else{
                    nums[i]=0;
                }
            }else {
                nums[i]=mlu/nums[i];
            }
        }
        return nums;
    }





















}









